#!/usr/env/bin python
# -*- coding: utf-8 -*-

# @Time    : 2020/7/12 10:03|10:03
# @Author  : yangdingyi
# @File    : 2020-07-12.174. 地下城游戏
# @Software: PyCharm
from typing import List


class Solution:
    def calculateMinimumHP(self, dungeon: List[List[int]]) -> int:
        ans = 0
        if not dungeon:
            return ans
        lm = len(dungeon)
        ln = len(dungeon[0])

        dp = [[None for i in range(ln + 1)] for j in range(lm + 1)]

        # step = [(0, 1), (1, 0)]
        # dp[0][0] = dungeon[0][0]
        # for i in range(lm):
        #     for j in range(ln):
        #         for si in range(2):
        #             x, y = i + step[si][0], j + step[si][1]
        #             if 0 <= x < lm and 0 <= y < ln:
        #                 if dp[x][y] is None or dp[i][j] + dungeon[x][y] > dp[x][y]:
        #                     dp[x][y] = dp[i][j] + dungeon[x][y]
        # ans = dp[ln-1][lm-1]
        # step = [(0, -1), (-1, 0)]
        # dp[lm-1][ln-1] = dungeon[lm-1][ln-1]
        dp[lm][ln-1] = 1
        dp[lm-1][ln] = 1
        for i in range(lm-1, -1, -1):
            for j in range(ln-1, -1, -1):
                if dp[i][j+1] is None:
                    mm = dp[i+1][j]
                elif dp[i+1][j] is None:
                    mm = dp[i][j+1]
                else:
                    mm = min(dp[i][j+1], dp[i+1][j])
                dp[i][j] = max(mm-dungeon[i][j], 1)
        # for i in range(len(dp)):
        #     print(list(map(lambda x: 0 if x is None else x, dp[i])))
        ans = dp[0][0]
        return ans


solve = Solution()

questions = [
    ([[-2, -3, 3], [-5, -10, 1], [10, 30, -5]],),
]

for qi, q in enumerate(questions):
    print(f'#{qi}:', q)
    print('ans:', solve.calculateMinimumHP(q[0]))
